Today, the availability of powerful digital computational tools has yielded the ability to present information in forms that go far beyond text and numbers. There now exists the capability to create and share data in more complex multimedia forms, using graphics, audio, still images and moving images (video), as well as combinations of those forms. This data may be a well-defined group of bits, such as a graphics/text file, an audio file or a still image file. The data may also be a real-time or near real-time bit stream of bits, such as that generated by live video, audio, or financial data.
Whether in file or stream format, however, multimedia data generally is far larger in size than text data. For example, whereas a conventional text file usually occupies less than 50 Kilobytes (Kbyte), just one minute of compressed video requires up to 10 Megabytes (Mbyte), almost 200 times larger in size. The presentation of information in multimedia form therefore creates two problems--storage and communication. Storage has improved dramatically over the past few years. For example, personal computers (PCs) can now store inexpensively many Gigabytes (Gbyte) of data, and the cost-per-Gbyte is becoming less expensive every day.
Communications, however, remain a problem. Historically, the oldest method of distributing large amounts of information has been printed material, usually in the form of magazines and books. However, this method is relatively expensive, takes days to complete, is limited to presenting data in text, pictorial or graphic form, and is difficult to update or change. Distribution of information via audio cassette or video cassette, while less costly and allowing information to be presented in audio and video form, is still relatively slow in that shipment of the physical item containing the information must take place, the cassette itself still makes it relatively difficult to update and change the information, and is incapable of communicating live video and audio.
More practical than printed material and cassettes, graphics, music and other information may be digitized into computer data files, referred to as "large digital objects," which in turn may be transferred from a host computer to a potentially large number of subscriber computers. One common way of transferring data files is via a public or private computer network, in which the data files are transmitted by the host computer and received by the subscriber computers over phone lines via a modem. Although distribution via modems may work well for multi-Kbyte files, transmitting multi-Mbyte data files is impractical even when using the fastest modems, because the transmission speed of modems is constrained by the relatively low bandwidth of the telephone lines. For example, reliably retrieving just one large data object using the Internet, or other public or private networks, even when using ISDN lines, may take many minutes to many hours, and is relatively expensive.
To avoid overloading expensive private networks, many companies distribute large text files and other large digital objects using CD-ROM disks, each of which can hold, for example, up to 660 Mbytes of data. While the cost of distribution is moderate in comparison to using a network, the distribution of CD-ROM disks suffers from one major drawback shared by the oldest methods of information distribution--it can take one or more days, in comparison to the theoretically near-instantaneous communication potential that digital information should enjoy. Further, to update this CD-ROM based information, new CD-ROMS must be provided, usually from every three months to a year.
Moreover, none of the above-described communication methods can be used to communicate quickly, efficiently and reliably streams of live data. For example, video may be stored on videotape prior to broadcast ("tape delay"). This is not acceptable, however, when users require the video immediately. Digital communication of live video or audio via the Internet is slow, unreliable and unwieldy. Traditional analog communication methods such as TV and radio, as well as the proposed digital TV, although quick and efficient, are very susceptible to noise and interference.
To overcome some of the problems associated with the above methods of distribution, distributors of large data files or long data streams are turning to satellite broadcasting. Satellite broadcasting provides not only distribution over large geographical areas, for example, the entire United States and Canada, but potentially has the high bandwidth capacity required to transmit large amounts of data at high speeds, thus reducing the transmission time to seconds. Moreover, the cost of satellite broadcasting, on a per-user basis, is comparatively less than the respective costs of the above methods.
One type of satellite broadcasting is one-way satellite broadcasting. A one-way broadcast satellite system, shown in FIG. 7, transfers data from a host computer 1 to a satellite transmitter device 2. The satellite transmitter device 2 in turn transmits, through an uplink antenna 4, the data to a satellite 5 using digital modulation techniques well-known in the art. The satellite 5 retransmits the data to one or more downlink antennas 6 and satellite receiver devices 7. The satellite receiver device 7 transfers the data to the subscriber computer 8.
One notable drawback of one-way satellite broadcast systems, however, as compared to some other methods of information distribution such as the above-described computer networks, is the inability of the subscriber computers to inform the host computer that a reception error has occurred. For example, if the information is live video, the display of the receiver will simply "freeze up" if an error is encountered, unable to continue until a correct frame of video is received. Thus, it is essential that the transferred data files or streams be received in perfect condition, or capable of being reconstructed to be in perfect condition, at all the subscriber computers.
The above drawback of one-way satellite broadcasting is further compounded, however, by the greater vulnerability of the broadcast signal to various forms of noise interference present in the transmission channel. One form of noise that is always present in the channel is "white" noise. For example, white noise is introduced in the satellite channel by the thermal radiation of the gaseous constituents of the earth's surface. The strength and frequency of this noise varies, and it sometimes overpowers the transmitted signal causing it to be received erroneously. Because of white noise, a transmitted binary "zero" bit is occasionally received erroneously as a binary "one" bit, and vice-versa. Such errors are known as bit errors. White noise generally tends to cause isolated bit errors in a transmitted message. Although these bit errors are usually spread out throughout the message, they can be easily detected and corrected, because they are isolated. In contrast with white noise, "impulse" noise tends to wipe out long sequences of consecutive bits. Such errors are known as "burst" errors. Their duration varies from a few milliseconds to a few seconds, but certain phenomena, such as rainstorms or sunspots, can cause burst errors of even longer duration such as a few minutes. Unlike bit errors due to white noise, burst errors are not distributed over the entire message, but only a portion thereof. However, burst errors are more difficult to detect and correct, because they wipe out so many consecutive bits of data.
Well-known error detection and correction (EDAC) schemes are used to reduce the effects of errors caused by white noise. EDAC generally operates at the bit level by adding enough redundant data bits to the data to detect and correct the received data. In practice, EDAC can only detect and correct a limited amount of bit errors. The redundant data added to the original data, however, obviously increases the amount of data to be transmitted and thus the transmission bandwidth and transmission time. Well-known EDAC schemes include Hamming, Viturbi, Reed-Solomon, and other forward error correction (FEC) coding schemes. Interleaving may also be performed at the bit level. Interleaving rearranges the data bits so that they are non-sequentially transmitted. The subscriber computer deinterleaves the received bits to reorder the bits as they originally appeared. This technique reduces the effect of errors in a sequence of bits. Although interleaving does not in itself correct those bit errors, by non-sequentially reordering the data bits in a block of data that is to be transmitted by the host computer, the bit errors are more uniformly distributed over the received block of data upon deinterleaving by the subscriber computer. By isolating the bit errors, interleaving enhances bit-level EDAC coding performance. Both EDAC and interleaving can also be performed on data symbols representing groups of bits, such as bytes.
In satellite broadcast systems, the transmitted data bits or symbols are most likely to be organized into large groups called packets, and a large data file is transmitted as a sequence of packets. The addressed subscriber computers reconstruct the large data file from the received packets. The above-described noise bursts, especially those due to rainstorms and sunspots, can typically damage one or more long sequences of consecutive packets. Those packets are either not received by one or more of the subscriber computers or are received severely corrupted. Although bit-level EDAC schemes might be able to correct some of the corrupted packets, depending on the number of erroneous bits in those corrupted packets, these schemes are simply not robust enough to correct the great majority of those corrupted packets. This is because, in extended periods of burst noise, a large amount of both the original data bits and redundant EDAC bits in a packet are received corrupted, thus making bit-level error correction, and thus packet-level error-correction, impossible. Moreover, EDAC schemes are useless in the case of those packets not received.
One known method for reducing the effect of burst errors in satellite broadcast systems is retransmission of those packets that were not received or were received corrupted and could not be corrected (hereinafter those packets are simply referred to as "lost"). For example, a host computer may broadcast via satellite to two geographically widely-separated subscriber computers A and B. Due to this wide separation, subscriber computer A and subscriber computer B may experience different weather conditions, and thus different patterns of noise. For example, subscriber computer A may lose 20% of the transmitted packets, while subscriber computer B may successfully receive all the transmitted packets. Although it is possible to rebroadcast the entire file to all the subscriber computers, this method is costly, wastes time and bandwidth, and prevents the satellite channel from being used for other purposes. In the above example, subscriber computer A would identify the lost packets (by examining the serial numbers of the correctly received packets) and would ask the host computer to retransmit the packets it missed until the entire large data file could be reconstructed perfectly by subscriber computer A. The request for missed packet retransmission is made through a back channel, and the host computer rebroadcasts those missed packets via satellite. Alternatively, the host computer retransmits those missed packets only to subscriber computer A through the back channel.
Retransmission of lost packets requires, however, (1) two-way communication back channels from all of the subscriber computers to the host computer so each subscriber computer can inform the host computer of which packets were lost, and (2) a retransmission protocol between the host computer and the subscriber computers. Each back channel usually takes the form of a modem and telephone lines, or is part of a standard computer network. The back channel therefore has a limited bandwidth and can timely transmit only a limited amount of information. Back channels are also expensive. Further, retransmission increases the time required to distribute the data, and prevents the host computer and subscriber computers from doing other tasks. In some applications, such as a mobile receiver, use of back channels may simply be impossible.
A reliable and efficient method for transferring large data files over a one-way broadcast satellite system to overcome many of the above-described problems is described in U.S. Pat. No. 6,012,159 (which, however, is not admitted to be prior art with respect to the present invention by its mention in this Background section). In that method, the data file to be broadcast is arranged into a first set of (original) packets in a host computer. A second set of packets, derived from the first set of packets, are transmitted by the host computer to the subscriber computers, which in turn receive all or some of the transmitted packets. Because of the innovative packet encoding technique described in that application, as long as the number of received packets is greater or equal to the number of original packets, the subscriber computer is able to reconstruct the entire original data file from the received packets. The techniques for encoding the transmitted packets from the original packets, and for decoding and reconstructing the original packets from the received packets, are set forth in that application and are incorporated herein by reference.
Although the packet-level encoding/decoding method of U.S. Pat. No. 6,012,159 provides for the reliable transfer of large data files from a host computer to one or more subscriber computers, broadcasting live data streams, as well as both data streams and files simultaneously, still presents a challenge, as follows. First, live data streams are not well-defined in size like data files, and thus, encoding and decoding stream data becomes a difficult task. Moreover, broadcasting live data streams, unlike static data files, requires the derivation of "pacing" information so that the data stream can be buffered and "played out" at the receiving end at the same rate it was generated at the transmitting end. This problem has not yet been addressed in any of the above-described communication methods. Further, control data may also be broadcast to control transmission by the transmitter, retransmission by the satellite and reception by the receiver. Authorization data that designates which subscribers are allowed to receive the broadcast data may also be required. Generally, control and authorization data are sent as a group of unencoded bits or packets preceding the information packets. An ill-timed noise burst, although not effecting the information packets, may wipe out most or all of this control or authorization data, which in turn may prevent the correct reception of the unaffected information data. This problem has also not been addressed in the any of the above-described communication methods.